package leecode;

/**
 * @author qingyan 2021-10-28
 */
public class Question45 {

    public static void main(String[] args) {
        Question45 question35 = new Question45();
        System.out.println(question35.jump(new int[]{2, 3, 1, 1, 4}));
    }

    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            //找能跳的最远的
            maxPosition = Math.max(maxPosition, nums[i] + i);
            if (i == end) { //遇到边界，就更新边界，并且步数加一
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    // 动态规划
    int dp(int[] nums) {
        // 每一步的最小步数
        int[] steps = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= Math.min(nums[i] + i, nums.length - 1); j++) {
                if (steps[j] == 0) {
                    steps[j] = steps[i] + 1;
                } else {
                    steps[j] = Math.min(steps[i] + 1, steps[j]);
                }
            }
        }
        return steps[nums.length - 1];
    }


}
